package pwd.allen;

public class OtherSort {

    /**
     * 直接插入排序
     * 原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
     *
     * 时间复杂度：
     *  平均：O(n^2) 最坏：O(n^2) 最好：O(n)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     *
     * @param array
     */
    public static void sortSimgleInsert(int[] array) {
        for (int i = 1; i < array.length; i++) {
            // 这里前(i-1)个数已经排好顺序了，准备将第i个数按顺序插入前(i-1)个数之中，
            int temp = array[i];
            int j = i - 1;
            for (; j >= 0 && array[j] > temp; j--) {
                array[j + 1] = array[j];
            }
            array[j + 1] = temp;
        }
    }

    /**
     * 希尔排序 简单插入排序的改进版
     * 原理：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序
     * 具体算法描述：
     *  选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
     *  按增量序列个数k，对序列进行k 趟排序；
     *  每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
     *
     * 时间复杂度：
     *  平均：O(n^1.3) 最坏：O(n^2) 最好：O(n)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     *
     * @param array
     */
    public static void sortShellInsert(int[] array) {
        int dl = array.length;
        while (true) {
            // dl为增量
            dl = (int) Math.ceil(dl / 2.0);
            // 按照dl将数组拆分成dl个子序列，对每个子序列进行直接插入排序
            for (int i = 0; i < dl; i++) {
                // 以dl为间隔进行直接插入排序
                for (int j = i + dl; j < array.length; j += dl) {
                    int temp = array[j];
                    int k = j - dl;
                    for (; k >= 0 && array[k] > temp; k -= dl) {
                        array[k + dl] = array[k];
                    }
                    array[k + dl] = temp;
                }
            }
            if (dl == 1) {
                break;
            }
        }
    }

    /**
     * 简单选择排序
     * 原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
     *  然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
     *
     * 时间复杂度：
     *  平均：O(n^2) 最坏：O(n^2) 最好：O(n^2)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     */
    public static void sortSimgleSelect(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[min] > array[j])
                    min = j;
            }
            if (min != i) {
                int temp = array[i];
                array[i] = array[min];
                array[min] = temp;
            }
        }
    }

}
